package com.LeeCode;

import java.util.*;

/**
 * 非递减子序列
 */

public class Code491 {
    public static void main(String[] args) {
        int[] nums = {4, 6, 7, 7};
        System.out.println(new Code491().findSubsequences(nums));
    }

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        Set<Integer>[] cnt = new HashSet[n];
        Arrays.setAll(cnt, i -> new HashSet<Integer>());
        backtrace(0, new ArrayList<>(), ans, cnt, nums);
        return ans;
    }

    private void backtrace(int index, List<Integer> list, List<List<Integer>> ans, Set<Integer>[] cnt, int[] nums) {
        // 从答案视角记录答案，元素个数至少为2
        if (list.size() >= 2)
            ans.add(new ArrayList<>(list));

        // 防止越界
        if (index == nums.length) return;

        int pos = list.size(); // 当前枚举子序列的哪一位
        for (int i = index; i < nums.length; i++) {
            if (cnt[pos].contains(nums[i])) {  // 子序列每个位置的数字只枚举一次
                continue;
            }
            if (pos != 0 && nums[i] < list.get(pos - 1)) { // 满足非递减序列
                continue;
            }

            cnt[pos].add(nums[i]); // 记录子序列该位置枚举过哪些数字
            list.add(nums[i]);
            backtrace(i + 1, list, ans, cnt, nums);
            list.remove(list.size() - 1); // 回溯
        }
        cnt[pos].clear(); // 回溯当前子序列位置记录过的数字
    }

    //======================================


    private int[] pre = new int[15];

    // 判重代码
    private boolean is_first(int[] nums, int last, int pos) {
        return !(last < pre[pos] && pre[pos] < pos);
    }

    private void dfs(int[] nums, int last, int pos, List<Integer> list, List<List<Integer>> ans) {
        if (nums.length == pos) {
            return; // 到达末尾，直接返回
        }

        // 检查 nums[pos] 是否符合要求
        if ((list.isEmpty() || nums[pos] >= list.get(list.size() - 1)) && is_first(nums, last, pos)) {
            list.add(nums[pos]);
            if (list.size() >= 2) { // 大于等于2了，那就放进去
                ans.add(new ArrayList<>(list));
            }
            dfs(nums, pos, pos + 1, list, ans); // 继续处理下一个
            list.remove(list.size() - 1); // 将当前放入的这个吐出来
        }
        dfs(nums, last, pos + 1, list, ans);
    }

    public List<List<Integer>> findSubsequences1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            pre[i] = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] == nums[i]) {
                    pre[i] = j;
                    break;
                }
            }
        }

        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(nums, -1, 0, list, ans);
        return ans;
    }
}
